package sort;

import java.util.Arrays;

public class HeapSort {
	public static void main(String[] args) {
		int[] arr={9,8,7,6,5,4,3,2,1};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
	public static void sort(int[] arr){
		//1.构建大顶堆
		for (int i = arr.length/2 -1; i>=0 ; i--) {
			//从第一个非叶子结点从下至上，从右至左调整结构
			adjustHeap(arr,i,arr.length);
		}

		//2.调整堆结构+交换堆顶元素与末尾元素
		for (int j = arr.length-1; j > 0 ; j--) {
			swap(arr,0,j);
			adjustHeap(arr,0,j);
		}
	}

	private static void adjustHeap(int[] arr, int i, int length) {
		int temp = arr[i];
		for(int k=i*2+1;k<length;k=k*2+1){
			//比较子节点的叶子节点，获取最大的下标
			if(k+1<length && arr[k] <arr[k+1]){
				k++;
			}
			if(arr[k] > temp){
				arr[i] = arr[k];
				i=k;
			}else{
				break;
			}
		}
		arr[i] = temp;
	}

	public static void swap(int[] arr,int a,int b){
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}
